#include "BTreeNode.h"

// TODO: Take out?
#include <iostream>

using namespace std;

#define DOUT if (0) cout

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
  int readStatus = pf.read(pid, buffer);
  inMemPid = pid;
  if (readStatus == 0)
  {
    memcpy(&numKeys, &buffer[PageFile::PAGE_SIZE - 2 * SIZE_OF_PID], sizeof(numKeys));
  }
  else
  {
    numKeys = 0;
    int nextPtr = -1;
    memcpy(&buffer[PageFile::PAGE_SIZE - SIZE_OF_PID], &nextPtr, SIZE_OF_PID);
  }

  return readStatus;
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
  memcpy(&buffer[PageFile::PAGE_SIZE - 2 * SIZE_OF_PID], &numKeys, sizeof(numKeys));
  return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
  return numKeys;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
  if (numKeys >= MAX_KEYS)
  {
    return RC_NODE_FULL;
  }

  // Figure out where in the buffer we need to store this entry.
  int eid = numKeys;
  locate(key, eid);
  int offset = eid * (sizeof(rid) + sizeof(key));

  // Shift over everything greater than the new entry one entry slot to make space.
  int numValidBytes = numKeys * SIZE_OF_ENTRY;
  int numBytesToShift = numValidBytes - offset;
  memmove(&buffer[offset + SIZE_OF_ENTRY], &buffer[offset], numBytesToShift);

  // Insert the new key, rid pairing.
  memcpy(&buffer[offset], &rid, sizeof(rid));
  memcpy(&buffer[offset + sizeof(rid)], &key, sizeof(key));

  numKeys += 1;
  return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid,
                              BTLeafNode& sibling, int& siblingKey)
{
  if (numKeys < MAX_KEYS)
  {
    return -1;
  }

  DOUT << "IAS Key: " << key << endl;
  int midway = (MAX_KEYS + 1) / 2;
  int offset = SIZE_OF_RID;
  int tempBufOffset = SIZE_OF_RID;
  char tempBuf[PageFile::PAGE_SIZE];
  bool insertedNewKey = false;
  bool insertedFirstKeyIntoSibling = false;
  int numCopies = 0;
  for (int i = 0; i < MAX_KEYS + 1; ++i)
  {
    int curKey;
    if (numCopies < MAX_KEYS)
    {
      memcpy(&curKey, &buffer[offset], sizeof(curKey));
    }
    if (i < midway)
    {
      if (curKey > key && !insertedNewKey)
      {
        memcpy(&tempBuf[tempBufOffset - SIZE_OF_RID], &rid, sizeof(rid));
        memcpy(&tempBuf[tempBufOffset], &key, sizeof(key));
        tempBufOffset += SIZE_OF_ENTRY;
        insertedNewKey = true;
      }
      else
      {
        memcpy(&tempBuf[tempBufOffset - SIZE_OF_RID], &buffer[offset - SIZE_OF_RID], SIZE_OF_RID);
        memcpy(&tempBuf[tempBufOffset], &curKey, sizeof(curKey));
        offset += SIZE_OF_ENTRY;
        numCopies += 1;
        tempBufOffset += SIZE_OF_ENTRY;
      }
    }
    else
    {
      DOUT << "IAS Key2: " << key << endl;
      if ((numCopies == MAX_KEYS  && !insertedNewKey) || (curKey > key && !insertedNewKey))
      {
        DOUT << "NODE: Inserting key: " << key << endl;
        sibling.insert(key, rid);
        insertedNewKey = true;
        if (!insertedFirstKeyIntoSibling)
        {
          siblingKey = key;
          insertedFirstKeyIntoSibling = true;
        }
      }
      else
      {
        RecordId ridToInsert;
        int keyToInsert;
        memcpy(&ridToInsert, &buffer[offset - SIZE_OF_RID], SIZE_OF_RID);
        memcpy(&keyToInsert, &buffer[offset], sizeof(curKey));
        DOUT << "NODE: Inserting key: " << keyToInsert << endl;
        sibling.insert(keyToInsert, ridToInsert);
        offset += SIZE_OF_ENTRY;
        numCopies += 1;
        if (!insertedFirstKeyIntoSibling)
        {
          siblingKey = keyToInsert;
          insertedFirstKeyIntoSibling = true;
        }
      }
    }
  }

  // Update the next node pointers accordingly.
  PageId endPtr;
  memcpy(&endPtr, &buffer[PageFile::PAGE_SIZE - SIZE_OF_PID], SIZE_OF_PID);
  sibling.setNextNodePtr(endPtr);


  // Copy temp buffer back into current node.
  memcpy(&buffer, &tempBuf, sizeof(tempBuf));
  numKeys = midway;
  setNextNodePtr(sibling.inMemPid);

  return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
  int entry = 0;
  int offset = SIZE_OF_RID;
  for (int i = 0; i < numKeys; ++i)
  {
    int key;
    memcpy(&key, &buffer[offset], sizeof(key));
    if (key >= searchKey)
    {
      eid = entry;
      return 0;
    }
    entry += 1;
    offset += SIZE_OF_ENTRY;
  }
  return -1;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
  int offset = eid * SIZE_OF_ENTRY;
  memcpy(&rid, &buffer[offset], sizeof(rid));
  memcpy(&key, &buffer[offset + sizeof(rid)], sizeof(key));
  return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
  PageId nextPtr;
  int offset = PageFile::PAGE_SIZE - SIZE_OF_PID;
  memcpy(&nextPtr, &buffer[offset], SIZE_OF_PID);
  return nextPtr;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
  int offset = PageFile::PAGE_SIZE - sizeof(pid);
  memcpy(&buffer[offset], &pid, sizeof(pid));
  return 0;
}

RC BTLeafNode::print()
{
  int offset = SIZE_OF_RID;
  for (int i = 0; i < numKeys; ++i)
  {
    int key;
    memcpy(&key, &buffer[offset], sizeof(key));
    DOUT << key << ",";
    offset += SIZE_OF_ENTRY;
  }
  DOUT << endl;
}

RC BTNonLeafNode::print()
{
  int offset = SIZE_OF_PID;
  for (int i = 0; i < numKeys; ++i)
  {
    int key;
    memcpy(&key, &buffer[offset], sizeof(key));
    DOUT << key << ",";
    offset += SIZE_OF_ENTRY;
  }
  DOUT << endl;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
  int readStatus = pf.read(pid, buffer);
  if (readStatus == 0)
  {
    memcpy(&numKeys, &buffer[PageFile::PAGE_SIZE - SIZE_OF_PID], sizeof(numKeys));
  }
  else
  {
    numKeys = 0;
  }
  return readStatus;
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
    memcpy(&buffer[PageFile::PAGE_SIZE - SIZE_OF_PID], &numKeys, sizeof(numKeys));
    return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
    return numKeys;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
  if (numKeys >= MAX_KEYS)
  {
    return RC_NODE_FULL;
  }

  // Figure out where in the buffer we need to store this entry.
  //int eid = numKeys;
  int eid;
  int offset = SIZE_OF_PID;
  for (eid = 0; eid < numKeys; ++eid)
  {
      int curKey;
      memcpy(&curKey, &buffer[offset], sizeof(curKey));

      if (curKey == key)
      {
          return 0;
      }
      else if(curKey > key)
      {
          break;
      }
      offset += SIZE_OF_ENTRY;
  }

  //locateChildPtr(key, eid);
  offset = sizeof(pid) + (eid * (sizeof(pid) + sizeof(key)));

  // Shift over everything greater than the new entry one entry slot to make space.
  int numValidBytes = numKeys * SIZE_OF_ENTRY + SIZE_OF_PID;
  int numBytesToShift = numValidBytes - offset;
  memmove(&buffer[offset + SIZE_OF_ENTRY], &buffer[offset], numBytesToShift);

  // Insert the new key, pid pairing.
  memcpy(&buffer[offset], &key, sizeof(key));
  memcpy(&buffer[offset + sizeof(key)], &pid, sizeof(pid));

  numKeys += 1;
  return 0;
}


/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 

  if (numKeys < MAX_KEYS)
  {
    return -1;
  }

  int midway = (MAX_KEYS + 1) / 2;
  int offset = SIZE_OF_PID;
  int tempBufOffset = SIZE_OF_PID;
  char tempBuf[PageFile::PAGE_SIZE];
  bool insertedNewKey = false;
  bool insertedMidPid = false;
  int numCopiesOrMoves = 0;
  PageId midPid = -1;

  memcpy(&tempBuf[0], &buffer[0], SIZE_OF_PID);

  for (int i = 0; i < MAX_KEYS + 1; ++i)
  {
    int curKey;
    memcpy(&curKey, &buffer[offset], sizeof(curKey));
    if (i < midway)
    {
      if (curKey > key && !insertedNewKey)
      {
        memcpy(&tempBuf[tempBufOffset], &key, sizeof(key));
        memcpy(&tempBuf[tempBufOffset + SIZE_OF_KEY], &pid, sizeof(pid));
        tempBufOffset += SIZE_OF_ENTRY;
        insertedNewKey = true;
      }
      else
      {
        memcpy(&tempBuf[tempBufOffset], &curKey, sizeof(curKey));
        memcpy(&tempBuf[tempBufOffset + SIZE_OF_KEY], &buffer[offset + SIZE_OF_KEY], SIZE_OF_PID);
        offset += SIZE_OF_ENTRY;
        tempBufOffset += SIZE_OF_ENTRY;
        numCopiesOrMoves += 1;
      }
    }
    else if (i == midway)
    {
      if (curKey > key && !insertedNewKey)
      {
        midKey = key;
        midPid = pid;
        insertedNewKey = true;
      }
      else
      {
        midKey = curKey;
        memcpy(&midPid, &buffer[offset + SIZE_OF_KEY], SIZE_OF_PID);
        offset += SIZE_OF_ENTRY;
        numCopiesOrMoves += 1;
      }
    }
    else
    {
      if ((numCopiesOrMoves == MAX_KEYS && !insertedNewKey) || (curKey > key && !insertedNewKey))
      {
        insertedNewKey = true;

        if (!insertedMidPid)
        {
          insertedMidPid = true;
          sibling.initializeRoot(midPid, key, pid);
        }
        else
        {
          sibling.insert(key, pid);
        }
      }
      else
      {
        PageId pidToInsert;
        int keyToInsert;
        memcpy(&keyToInsert, &buffer[offset], sizeof(curKey));
        memcpy(&pidToInsert, &buffer[offset + SIZE_OF_KEY], SIZE_OF_PID);
         if (!insertedMidPid)
        {
          insertedMidPid = true;
          sibling.initializeRoot(midPid, keyToInsert, pidToInsert);
        }
        else
        {
          sibling.insert(keyToInsert, pidToInsert);
        }
        offset += SIZE_OF_ENTRY;
        numCopiesOrMoves += 1;
      }
    }
  }
  // Copy temp buffer back into current node.
  memcpy(&buffer, &tempBuf, sizeof(tempBuf));
  numKeys = midway;

}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
    int offset = SIZE_OF_PID;
    for (int i = 0; i < numKeys; ++i) 
    {
        int key;
        memcpy(&key, &buffer[offset], sizeof(key));
        if (key > searchKey)
        {
            memcpy(&pid, &buffer[offset-SIZE_OF_PID], sizeof(pid));
            return 0;
        }
        offset += SIZE_OF_ENTRY;
    }
    memcpy(&pid, &buffer[offset-SIZE_OF_PID], sizeof(pid));
    return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
    memcpy(&buffer[0], &pid1, sizeof(pid1));
    memcpy(&buffer[SIZE_OF_PID], &key, sizeof(key));
    memcpy(&buffer[SIZE_OF_PID+SIZE_OF_KEY], &pid2, sizeof(pid2));
    numKeys += 1;
    return 0;
}
